//给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "aba"
//输出: true
// 
//
// 示例 2： 
//
// 
//输入: s = "abca"
//输出: true
//解释: 可以删除 "c" 字符 或者 "b" 字符
// 
//
// 示例 3： 
//
// 
//输入: s = "abc"
//输出: false 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁵ 
// s 由小写英文字母组成 
// 
//
// 
//
// 
// 注意：本题与主站 680 题相同： https://leetcode-cn.com/problems/valid-palindrome-ii/ 
//
// Related Topics 贪心 双指针 字符串 👍 88 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-01-17 19:58:38
 * @description LCR 019.验证回文串 II
 
 */
 
public class RQku0D {
    public static void main(String[] args) {
    //测试代码
    RQku0D fun = new RQku0D();
    Solution solution= fun.new Solution();
        System.out.println(solution.validPalindrome("aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //abbca abcca
        public boolean validPalindrome(String s) {
            return validPalindromeHelper(s, 0, s.length() - 1, false);
        }

    private boolean validPalindromeHelper(String s, int l, int r, boolean del) {
        while (l <= r) {
            if (s.charAt(l) != s.charAt(r)) {
                if (del) {
                    return false;
                }
                // 分两种情况跳过字符
                return validPalindromeHelper(s, l + 1, r, true) || validPalindromeHelper(s, l, r - 1, true);
            }
            l++;
            r--;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
